package com.computer.fundamentals.algorithm;

import com.computer.util.Constant;

/**
 * KMP算法
 * 一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的
 */
public class KnuthMorrisPratt {

    /**
     * 字符串匹配-KMP算法
     */
    public int strStr(String mainStr, String pattern) {
        if (mainStr == null || mainStr.equals("")) {
            throw new RuntimeException(Constant.MAIN_STRING_IS_NULL);
        }
        if (pattern == null || pattern.length() == 0) {
            throw new RuntimeException(Constant.PATTERN_IS_NULL);
        }
        if (mainStr.length() < pattern.length()) {
            throw new RuntimeException(Constant.MAIN_STRING_LESS_THAN_PATTERN_IN_LENGTH);
        }

        int[] next = patternNext(pattern);
        int j = 0;
        for (int i = 0;i < mainStr.length();i++) {
            while (j > 0 && mainStr.charAt(i) != pattern.charAt(j)) {
                j = next[j-1];
            }
            if (mainStr.charAt(i) == pattern.charAt(j)) {
                j++;
                if (j == pattern.length()) {
                    return i-j+1;
                }
            }
        }

        return -1;
    }

    /**
     * 模式串的前后缀跳跃数组
     */
    private int[] patternNext(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;
        for (int i = 1;i < pattern.length();i++) {
            while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = next[j-1];
            }
            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        KnuthMorrisPratt knuthMorrisPratt = new KnuthMorrisPratt();
        System.out.println("------------测试字符串------------");
        String mainString = "adcadcaddcadde";
        String pattern = "adcadde";
        System.out.println("主串=" + mainString + ", " + "模式串=" + pattern);
        System.out.println("\n");

        System.out.println("------------结果------------");
        int res = knuthMorrisPratt.strStr(mainString, pattern);
        System.out.println(res);

    }
}